package cn.liucl.code.leetcode;

import java.util.*;

public class Topic1481 {

    public static void main(String[] args) {
        //int[] arr ={4,3,1,1,3,3,2};int k = 3;
        int[] arr = {2, 4, 1, 8, 3, 5, 1, 3};
        int k = 3;
        int leastNumOfUniqueInts = findLeastNumOfUniqueInts(arr, k);
        System.out.println(leastNumOfUniqueInts);
    }

    /**
     * 1481. 不同整数的最少数目
     * 给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。
     * 示例 1：
     * <p>
     * 输入：arr = [5,5,4], k = 1
     * 输出：1
     * 解释：移除 1 个 4 ，数组中只剩下 5 一种整数。
     * 示例 2：
     * <p>
     * 输入：arr = [4,3,1,1,3,3,2], k = 3
     * 输出：2
     * 解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/least-number-of-unique-integers-after-k-removals
     */
    public static int findLeastNumOfUniqueInts(int[] arr, int k) {
        //1.统计数组中没个数字出现的次数
        Map<Integer, Integer> map = new TreeMap<>();
        for (int i : arr) {
            map.merge(i, 1, Integer::sum);
        }
        //2.按出现次数，排序，并查出是那些数字
        Map<Integer, List<Integer>> count = new TreeMap<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (count.get(entry.getValue()) == null) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(entry.getKey());
                count.put(entry.getValue(), list);
            } else {
                count.get(entry.getValue()).add(entry.getKey());
            }
        }
        //3.按最少出现次数的数字，移除
        int remove = 0;//移除的数字 个数
        List<Integer> removeList = new ArrayList<>();//移除的数字
        for (Map.Entry<Integer, List<Integer>> entry : count.entrySet()) {
            //这个数量的数字，全部移除，还没有达到移除量
            if (remove + entry.getValue().size() * entry.getKey() <= k) {
                removeList.addAll(entry.getValue());
                remove += entry.getValue().size() * entry.getKey();
            } else {
                for (Integer integer : entry.getValue()) {
                    if (remove + entry.getKey() <= k) {
                        removeList.add(integer);
                        remove += entry.getKey();
                    }
                }
                break;
            }
        }
        return map.size() - removeList.size();
    }
}
